package lc_剑指_Offer_II_053_二叉搜索树中的中序后继;

import java.util.Stack;

public class Solution {

	/**
	 * Definition for a binary tree node.
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root, pre = null;
		while (!stack.isEmpty() || node != null) {
			while (node != null) {
				stack.add(node);
				node = node.left;
			}
			TreeNode cur = stack.pop();
			if (pre == p) {
				return cur;
			}
			pre = cur;
			node = cur.right;
		}
		return null;
	}
}